package topcoderme;

import java.util.*;
import java.util.logging.Level;
import java.util.logging.Logger;
import java.util.regex.*;
import java.text.*;
import java.math.*;

public class MultiplesWithLimit {

    public String minMultiples(int N, int[] forbiddenDigits) {
        boolean[] vis = new boolean[(int) 1e6];
        int msk = 0;
        for (int x : forbiddenDigits) {
            msk |= (1 << x);
        }
        Queue<BigInteger> Q = new LinkedList<BigInteger>();
        Q.add(BigInteger.ZERO);

        while (Q.isEmpty() == false) {
            BigInteger curNum = Q.poll();
            for (int i = 0; i <= 9; ++i) {
                if ((msk & (1 << i)) == 0) {
                    BigInteger toInsert = curNum.multiply(BigInteger.TEN).add(new BigInteger("" + i));
                    int modValue = toInsert.mod(BigInteger.valueOf((long) N)).intValue();
                    if (toInsert.equals(BigInteger.ZERO) == true) {
                        continue;
                    }
                    if (modValue == 0) {
                        String res = toInsert.toString();
                        if (res.length() < 9) {
                            return res;
                        } else {
                            return res.substring(0, 3) + "..." + res.substring(res.length() - 3) + "(" + res.length() + " digits)";
                        }
                    }
                    if (vis[modValue] == false) {
                        Q.add(toInsert);
                        vis[modValue] = true;
                    }
                }
            }
        }
        return "IMPOSSIBLE";
    }

    // BEGIN KAWIGIEDIT TESTING
    // Generated by KawigiEdit 2.1.8 (beta) modified by pivanof
    private static boolean KawigiEdit_RunTest(int testNum, int p0, int[] p1, boolean hasAnswer, String p2) {
        System.out.print("Test " + testNum + ": [" + p0 + "," + "{");
        for (int i = 0; p1.length > i; ++i) {
            if (i > 0) {
                System.out.print(",");
            }
            System.out.print(p1[i]);
        }
        System.out.print("}");
        System.out.println("]");
        MultiplesWithLimit obj;
        String answer;
        obj = new MultiplesWithLimit();
        long startTime = System.currentTimeMillis();
        answer = obj.minMultiples(p0, p1);
        long endTime = System.currentTimeMillis();
        boolean res;
        res = true;
        System.out.println("Time: " + (endTime - startTime) / 1000.0 + " seconds");
        if (hasAnswer) {
            System.out.println("Desired answer:");
            System.out.println("\t" + "\"" + p2 + "\"");
        }
        System.out.println("Your answer:");
        System.out.println("\t" + "\"" + answer + "\"");
        if (hasAnswer) {
            res = answer.equals(p2);
        }
        if (!res) {
            System.out.println("DOESN'T MATCH!!!!");
        } else if ((endTime - startTime) / 1000.0 >= 2) {
            System.out.println("FAIL the timeout");
            res = false;
        } else if (hasAnswer) {
            System.out.println("Match :-)");
        } else {
            System.out.println("OK, but is it right?");
        }
        System.out.println("");
        return res;
    }

    public static void main(String[] args) {
        boolean all_right;
        all_right = true;

        int p0;
        int[] p1;
        String p2;

        // ----- test 0 -----
        p0 = 8;
        p1 = new int[]{2, 3, 4, 5, 6, 7, 8, 9};
        p2 = "1000";
        all_right = KawigiEdit_RunTest(0, p0, p1, true, p2) && all_right;
        // ------------------

        // ----- test 1 -----
        p0 = 9;
        p1 = new int[]{1, 3, 4, 5, 6, 7, 8, 9};
        p2 = "222...222(9 digits)";
        all_right = KawigiEdit_RunTest(1, p0, p1, true, p2) && all_right;
        // ------------------

        // ----- test 2 -----
        p0 = 524;
        p1 = new int[]{5, 2, 4};
        p2 = "3668";
        all_right = KawigiEdit_RunTest(2, p0, p1, true, p2) && all_right;
        // ------------------

        // ----- test 3 -----
        p0 = 10000;
        p1 = new int[]{0};
        p2 = "IMPOSSIBLE";
        all_right = KawigiEdit_RunTest(3, p0, p1, true, p2) && all_right;
        // ------------------

        // ----- test 4 -----
        p0 = 1;
        p1 = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        p2 = "IMPOSSIBLE";
        all_right = KawigiEdit_RunTest(4, p0, p1, true, p2) && all_right;
        // ------------------

        if (all_right) {
            System.out.println("You're a stud (at least on the example cases)!");
        } else {
            System.out.println("Some of the test cases had errors.");
        }
    }
    // END KAWIGIEDIT TESTING
}
//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!

